package LeetCodeHot100TopInterview;

import java.util.LinkedList;
import java.util.List;

public class Q131_PalindromePartitioning {
    //给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 返回 s 所有可能的分割方案
    //回文串 是正着读和反着读都一样的字符串

    //大流程  前缀枚举 + dp + dfs
    public List<List<String>> partition(String s) {

        //L -> R是否回文
        boolean[][] dp = getDP(s);
        List<List<String>> ans = new LinkedList<>();
        process(s, 0, new LinkedList<>(), ans, dp);
        return ans;
    }

    //经典过程
    public void process(String s, int index, LinkedList<String> path, List<List<String>> ans, boolean[][] dp){
        //base case
        //结尾收集打哪处
        if (index == s.length()){
            ans.add(new LinkedList<>(path));
            return;
        }

        //全排列变种
        for (int end = index; end < s.length(); end++) {
            //怎么决策??
            if (dp[index][end]){
                //左闭右开
                path.addLast(s.substring(index, end + 1));
                process(s, end + 1, path, ans, dp);
                //恢复现场
                path.removeLast();
            }
        }
    }

    //判断 L->R 是否回文
    public boolean[][] getDP(String s){
        //左下角弃而不用
        boolean[][] dp = new boolean[s.length()][s.length()];
        char[] str = s.toCharArray();
        int N = s.length();
        //填对角线 单个字符都是回文
        for (int i = 0; i < N; i++) {
            dp[i][i] = true;
        }
        //填倒数第二条对角线
        //直接看数据状况就好了
        for (int i = 0; i < N - 1; i++) {
            dp[i][i + 1] = str[i] == str[i + 1];
        }
        //填充其余的
        //L .. R 是否回文取决于 [L] == [R] 与 dp[L + 1][R - 1]
        //每次一斜线

        for (int i = 2; i < N; i++) {
            int row = 0;
            int col = i;
            while (row < N && col < N){
                dp[row][col] = str[row] == str[col] && dp[row + 1][col - 1];
                row++;
                col++;
            }
        }
        return dp;
    }


}
